#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdarg.h>

// ========================= 核心类型修正：用void*模拟Object =========================
// C语言中用void*模拟Java的Object，支持任意类型数据
typedef void* Object;

// ========================= 类型定义与工具函数 =========================
// 置换表达式虚表（模拟Java接口）
typedef struct DisplaceExpression DisplaceExpression;
typedef struct {
    // 应用置换：返回新数组（调用者需释放）
    Object* (*apply)(const DisplaceExpression* self, const Object* array, int len);
    // 化简置换表达式：返回新的化简后实例（调用者需释放）
    DisplaceExpression* (*simplify)(const DisplaceExpression* self);
    // 获取所有涉及的位置集合：返回动态数组（int[]），长度通过out_len输出（调用者需释放）
    int* (*get_positions)(const DisplaceExpression* self, int* out_len);
    // 获取某个位置的下一个位置
    int (*get_next)(const DisplaceExpression* self, int pos);
    // 释放实例内存
    void (*destroy)(DisplaceExpression* self);
} DisplaceVTable;

// 置换表达式基类（所有具体置换的父结构）
struct DisplaceExpression {
    const DisplaceVTable* vtable;
};

// 工具函数：创建新数组并拷贝原数组内容（对应Java System.arraycopy）
// 注意：仅拷贝指针地址，不深拷贝数据（如需深拷贝，需用户自行处理）
Object* copy_array(const Object* array, int len) {
    Object* new_arr = (Object*)malloc(len * sizeof(Object));
    if (new_arr) {
        memcpy(new_arr, array, len * sizeof(Object));
    }
    return new_arr;
}

// 工具函数：动态数组（用于存储位置集合、子表达式等）
typedef struct {
    void** data;
    int size;
    int capacity;
} DynamicArray;

DynamicArray* da_init(int init_capacity) {
    DynamicArray* da = (DynamicArray*)malloc(sizeof(DynamicArray));
    if (!da) return NULL;
    da->capacity = init_capacity > 0 ? init_capacity : 4;
    da->data = (void**)malloc(da->capacity * sizeof(void*));
    da->size = 0;
    return da;
}

void da_add(DynamicArray* da, void* elem) {
    if (!da) return;
    if (da->size >= da->capacity) {
        da->capacity *= 2;
        void** new_data = (void**)realloc(da->data, da->capacity * sizeof(void*));
        if (!new_data) return;
        da->data = new_data;
    }
    da->data[da->size++] = elem;
}

void da_destroy(DynamicArray* da, void (*free_elem)(void*)) {
    if (!da) return;
    if (free_elem) {
        for (int i = 0; i < da->size; i++) {
            free_elem(da->data[i]);
        }
    }
    free(da->data);
    free(da);
}

// 工具函数：排序int数组（模拟TreeMap的有序性）
void sort_int_array(int* arr, int len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// ========================= 恒等置换（单例） =========================
typedef struct {
    DisplaceExpression base; // 继承基类
} EmptyDisplaceExpression;

// 恒等置换单例实例
static EmptyDisplaceExpression s_empty_instance;
static bool s_empty_inited = false;

// 恒等置换apply：直接返回原数组拷贝（符合「返回新数组」语义）
static Object* empty_apply(const DisplaceExpression* self, const Object* array, int len) {
    return copy_array(array, len);
}

// 恒等置换simplify：返回自身（已最简）
static DisplaceExpression* empty_simplify(const DisplaceExpression* self) {
    // 单例无需拷贝，直接返回指针
    return (DisplaceExpression*)&s_empty_instance;
}

// 恒等置换get_positions：返回空数组
static int* empty_get_positions(const DisplaceExpression* self, int* out_len) {
    *out_len = 0;
    return NULL;
}

// 恒等置换get_next：返回自身位置
static int empty_get_next(const DisplaceExpression* self, int pos) {
    return pos;
}

// 恒等置换destroy：单例不释放内存
static void empty_destroy(DisplaceExpression* self) {
    // 单例模式，避免误释放
}

// 恒等置换虚表
static const DisplaceVTable s_empty_vtable = {
    .apply = empty_apply,
    .simplify = empty_simplify,
    .get_positions = empty_get_positions,
    .get_next = empty_get_next,
    .destroy = empty_destroy
};

// 获取恒等置换单例
DisplaceExpression* EmptyDisplaceExpression_getInstance() {
    if (!s_empty_inited) {
        s_empty_instance.base.vtable = &s_empty_vtable;
        s_empty_inited = true;
    }
    return (DisplaceExpression*)&s_empty_instance;
}

// ========================= 轮换置换 =========================
typedef struct {
    DisplaceExpression base; // 继承基类
    int* cyclic;             // 轮换位置数组（如[1,2,3]）
    int cyclic_len;          // 数组长度
} CyclicDisplaceExpression;

// 轮换置换apply：从后往前遍历，处理首尾元素（核心逻辑不变，仅修正类型）
static Object* cyclic_apply(const DisplaceExpression* self, const Object* array, int len) {
    const CyclicDisplaceExpression* cyclic = (const CyclicDisplaceExpression*)self;
    Object* new_arr = copy_array(array, len);
    if (!new_arr || cyclic->cyclic_len <= 1) {
        return new_arr; // 长度≤1的轮换等同于恒等置换
    }

    // 原Java逻辑：保存最后一个位置的值，从后往前赋值，最后给第一个位置赋值
    Object temp = array[cyclic->cyclic[cyclic->cyclic_len - 1]];
    for (int i = cyclic->cyclic_len - 1; i > 0; i--) {
        int curr_pos = cyclic->cyclic[i];
        int prev_pos = cyclic->cyclic[i - 1];
        if (curr_pos >= len || prev_pos >= len) {
            free(new_arr);
            return NULL; // 位置超出数组范围，返回NULL表示错误
        }
        new_arr[curr_pos] = array[prev_pos];
    }
    new_arr[cyclic->cyclic[0]] = temp;

    return new_arr;
}

// 轮换置换simplify：自身已最简，返回拷贝
static DisplaceExpression* cyclic_simplify(const DisplaceExpression* self) {
    const CyclicDisplaceExpression* cyclic = (const CyclicDisplaceExpression*)self;
    // 创建新的轮换实例作为化简结果
    return (DisplaceExpression*)CyclicDisplaceExpression_create(cyclic->cyclic, cyclic->cyclic_len);
}

// 轮换置换get_positions：返回轮换位置数组的拷贝
static int* cyclic_get_positions(const DisplaceExpression* self, int* out_len) {
    const CyclicDisplaceExpression* cyclic = (const CyclicDisplaceExpression*)self;
    *out_len = cyclic->cyclic_len;
    int* positions = (int*)malloc(*out_len * sizeof(int));
    if (positions) {
        memcpy(positions, cyclic->cyclic, *out_len * sizeof(int));
    }
    return positions;
}

// 轮换置换get_next：获取某个位置的下一个位置（循环）
static int cyclic_get_next(const DisplaceExpression* self, int pos) {
    const CyclicDisplaceExpression* cyclic = (const CyclicDisplaceExpression*)self;
    for (int i = 0; i < cyclic->cyclic_len; i++) {
        if (cyclic->cyclic[i] == pos) {
            // 最后一个位置的下一个是第一个位置
            return cyclic->cyclic[(i + 1) % cyclic->cyclic_len];
        }
    }
    return pos; // 不在轮换中的位置，返回自身
}

// 轮换置换destroy：释放位置数组
static void cyclic_destroy(DisplaceExpression* self) {
    CyclicDisplaceExpression* cyclic = (CyclicDisplaceExpression*)self;
    free(cyclic->cyclic);
    free(cyclic);
}

// 轮换置换虚表
static const DisplaceVTable s_cyclic_vtable = {
    .apply = cyclic_apply,
    .simplify = cyclic_simplify,
    .get_positions = cyclic_get_positions,
    .get_next = cyclic_get_next,
    .destroy = cyclic_destroy
};

// 创建轮换置换实例（工厂函数）
CyclicDisplaceExpression* CyclicDisplaceExpression_create(const int* cyclic, int len) {
    if (len <= 0 || !cyclic) return NULL;
    CyclicDisplaceExpression* expr = (CyclicDisplaceExpression*)malloc(sizeof(CyclicDisplaceExpression));
    if (!expr) return NULL;

    expr->cyclic = (int*)malloc(len * sizeof(int));
    if (!expr->cyclic) {
        free(expr);
        return NULL;
    }
    memcpy(expr->cyclic, cyclic, len * sizeof(int));
    expr->cyclic_len = len;
    expr->base.vtable = &s_cyclic_vtable;

    return expr;
}

// ========================= 轮换组合置换（组合模式） =========================
typedef struct {
    DisplaceExpression base;   // 继承基类
    DynamicArray* expressions; // 子表达式集合（DisplaceExpression*数组）
} CompositeDisplaceExpression;

// 组合置换apply：遍历子表达式，依次应用置换（类型修正）
static Object* composite_apply(const DisplaceExpression* self, const Object* array, int len) {
    const CompositeDisplaceExpression* composite = (const CompositeDisplaceExpression*)self;
    if (composite->expressions->size == 0) {
        return copy_array(array, len); // 无子女等同于恒等置换
    }

    // 依次应用每个子表达式，注意释放中间数组
    Object* result = copy_array(array, len);
    if (!result) return NULL;

    for (int i = 0; i < composite->expressions->size; i++) {
        DisplaceExpression* sub_expr = (DisplaceExpression*)composite->expressions->data[i];
        Object* temp = sub_expr->vtable->apply(sub_expr, result, len);
        free(result);
        result = temp;
        if (!result) break; // 某个子表达式执行失败，返回NULL
    }

    return result;
}

// 组合置换simplify：核心化简逻辑（复刻Java代码，仅修正类型相关）
static DisplaceExpression* composite_simplify(const DisplaceExpression* self) {
    const CompositeDisplaceExpression* composite = (const CompositeDisplaceExpression*)self;

    // 步骤1：收集所有涉及的位置，构建位置映射表（pos → next_pos）
    DynamicArray* pos_map = da_init(8); // 存储键值对：int[2] = {pos, next_pos}
    DynamicArray* all_positions = da_init(8);

    // 1.1 收集所有位置
    for (int i = 0; i < composite->expressions->size; i++) {
        DisplaceExpression* sub_expr = (DisplaceExpression*)composite->expressions->data[i];
        int pos_len = 0;
        int* positions = sub_expr->vtable->get_positions(sub_expr, &pos_len);
        for (int j = 0; j < pos_len; j++) {
            // 去重添加位置
            bool exists = false;
            for (int k = 0; k < all_positions->size; k++) {
                if (*(int*)all_positions->data[k] == positions[j]) {
                    exists = true;
                    break;
                }
            }
            if (!exists) {
                int* pos_ptr = (int*)malloc(sizeof(int));
                *pos_ptr = positions[j];
                da_add(all_positions, pos_ptr);
            }
        }
        free(positions);
    }

    // 1.2 构建位置映射（过滤自映射）
    for (int i = 0; i < all_positions->size; i++) {
        int pos = *(int*)all_positions->data[i];
        int next_pos = composite->base.vtable->get_next(self, pos); // 组合的next是所有子表达式依次应用的结果
        if (pos != next_pos) {
            int* kv = (int*)malloc(2 * sizeof(int));
            kv[0] = pos;
            kv[1] = next_pos;
            da_add(pos_map, kv);
        }
    }

    // 步骤2：按映射表提取循环，生成最简轮换
    DynamicArray* simplified = da_init(4);
    while (pos_map->size > 0) {
        // 取第一个映射作为循环起点
        int* first_kv = (int*)pos_map->data[0];
        int start_pos = first_kv[0];
        DynamicArray* cyclic_pos = da_init(4);

        // 遍历循环链
        int curr_pos = start_pos;
        while (true) {
            // 查找curr_pos在映射表中的位置
            int kv_idx = -1;
            for (int i = 0; i < pos_map->size; i++) {
                int* kv = (int*)pos_map->data[i];
                if (kv[0] == curr_pos) {
                    kv_idx = i;
                    break;
                }
            }
            if (kv_idx == -1) break;

            // 添加到当前循环
            int* pos_ptr = (int*)malloc(sizeof(int));
            *pos_ptr = curr_pos;
            da_add(cyclic_pos, pos_ptr);

            // 从映射表中移除该映射
            free(pos_map->data[kv_idx]);
            // 移动后续元素覆盖
            for (int i = kv_idx; i < pos_map->size - 1; i++) {
                pos_map->data[i] = pos_map->data[i + 1];
            }
            pos_map->size--;

            // 获取下一个位置（注意：移除前已保存next_pos）
            int next_pos = first_kv[1];
            if (kv_idx > 0) {
                next_pos = ((int*)pos_map->data[kv_idx - 1])[1];
            }
            curr_pos = next_pos;
            if (curr_pos == start_pos) break;
        }

        // 生成轮换表达式（循环长度≥2才有效）
        if (cyclic_pos->size >= 2) {
            int* cyclic_arr = (int*)malloc(cyclic_pos->size * sizeof(int));
            for (int i = 0; i < cyclic_pos->size; i++) {
                cyclic_arr[i] = *(int*)cyclic_pos->data[i];
            }
            // 排序循环位置（保持与Java TreeMap一致的有序性）
            sort_int_array(cyclic_arr, cyclic_pos->size);
            DisplaceExpression* cyclic_expr = (DisplaceExpression*)CyclicDisplaceExpression_create(cyclic_arr, cyclic_pos->size);
            da_add(simplified, cyclic_expr);
            free(cyclic_arr);
        }

        // 释放循环位置数组
        da_destroy(cyclic_pos, free);
    }

    // 步骤3：生成化简结果
    DisplaceExpression* result;
    if (simplified->size == 0) {
        result = EmptyDisplaceExpression_getInstance(); // 无有效轮换，返回恒等置换
    } else if (simplified->size == 1) {
        result = (DisplaceExpression*)simplified->data[0]; // 单个轮换，直接返回
        simplified->data[0] = NULL; // 避免被da_destroy释放
    } else {
        // 多个轮换，生成新的组合表达式
        // 先将DynamicArray转换为数组
        DisplaceExpression** sub_exprs = (DisplaceExpression**)malloc(simplified->size * sizeof(DisplaceExpression*));
        for (int i = 0; i < simplified->size; i++) {
            sub_exprs[i] = (DisplaceExpression*)simplified->data[i];
            simplified->data[i] = NULL; // 避免重复释放
        }
        result = (DisplaceExpression*)CompositeDisplaceExpression_create(simplified->size, sub_exprs);
        free(sub_exprs);
    }

    // 释放临时资源
    da_destroy(pos_map, free);
    da_destroy(all_positions, free);
    da_destroy(simplified, NULL);

    return result;
}

// 组合置换get_positions：收集所有子表达式的位置并去重
static int* composite_get_positions(const DisplaceExpression* self, int* out_len) {
    const CompositeDisplaceExpression* composite = (const CompositeDisplaceExpression*)self;
    DynamicArray* positions = da_init(8);

    for (int i = 0; i < composite->expressions->size; i++) {
        DisplaceExpression* sub_expr = (DisplaceExpression*)composite->expressions->data[i];
        int sub_len = 0;
        int* sub_pos = sub_expr->vtable->get_positions(sub_expr, &sub_len);
        for (int j = 0; j < sub_len; j++) {
            // 去重
            bool exists = false;
            for (int k = 0; k < positions->size; k++) {
                if (*(int*)positions->data[k] == sub_pos[j]) {
                    exists = true;
                    break;
                }
            }
            if (!exists) {
                int* pos_ptr = (int*)malloc(sizeof(int));
                *pos_ptr = sub_pos[j];
                da_add(positions, pos_ptr);
            }
        }
        free(sub_pos);
    }

    // 转换为int数组并排序
    *out_len = positions->size;
    int* result = (int*)malloc(*out_len * sizeof(int));
    if (result) {
        for (int i = 0; i < *out_len; i++) {
            result[i] = *(int*)positions->data[i];
        }
        sort_int_array(result, *out_len);
    }

    da_destroy(positions, free);
    return result;
}

// 组合置换get_next：依次应用所有子表达式，得到最终位置
static int composite_get_next(const DisplaceExpression* self, int pos) {
    const CompositeDisplaceExpression* composite = (const CompositeDisplaceExpression*)self;
    int curr_pos = pos;
    for (int i = 0; i < composite->expressions->size; i++) {
        DisplaceExpression* sub_expr = (DisplaceExpression*)composite->expressions->data[i];
        curr_pos = sub_expr->vtable->get_next(sub_expr, curr_pos);
    }
    return curr_pos;
}

// 组合置换destroy：释放子表达式和动态数组
static void composite_destroy(DisplaceExpression* self) {
    CompositeDisplaceExpression* composite = (CompositeDisplaceExpression*)self;
    // 释放所有子表达式
    for (int i = 0; i < composite->expressions->size; i++) {
        DisplaceExpression* sub_expr = (DisplaceExpression*)composite->expressions->data[i];
        sub_expr->vtable->destroy(sub_expr);
    }
    da_destroy(composite->expressions, NULL);
    free(composite);
}

// 组合置换虚表
static const DisplaceVTable s_composite_vtable = {
    .apply = composite_apply,
    .simplify = composite_simplify,
    .get_positions = composite_get_positions,
    .get_next = composite_get_next,
    .destroy = composite_destroy
};

// 创建组合置换实例（工厂函数）：接收子表达式数组
CompositeDisplaceExpression* CompositeDisplaceExpression_create(int sub_count, DisplaceExpression** sub_exprs) {
    CompositeDisplaceExpression* expr = (CompositeDisplaceExpression*)malloc(sizeof(CompositeDisplaceExpression));
    if (!expr) return NULL;

    expr->expressions = da_init(sub_count);
    if (!expr->expressions) {
        free(expr);
        return NULL;
    }

    // 添加子表达式
    for (int i = 0; i < sub_count; i++) {
        if (sub_exprs[i]) {
            da_add(expr->expressions, sub_exprs[i]);
        }
    }

    expr->base.vtable = &s_composite_vtable;
    return expr;
}

// ========================= 测试代码（用int类型示例，支持任意类型） =========================
// 辅助函数：打印int类型数组（用于测试）
void print_int_array(const Object* array, int len) {
    printf("[");
    for (int i = 0; i < len; i++) {
        printf("%d", *(int*)array[i]);
        if (i != len - 1) {
            printf(", ");
        }
    }
    printf("]\n");
}

void test_cyclic_apply() {
    printf("=== 测试轮换置换apply ===\n");
    // 轮换 M(1,2,3)：位置1→2→3→1（数组索引从0开始）
    int cyclic_pos[] = {1, 2, 3};
    DisplaceExpression* cyclic = (DisplaceExpression*)CyclicDisplaceExpression_create(cyclic_pos, 3);

    // 测试数组 {1,2,3,4}（用int*模拟Object，存储数据地址）
    int data[] = {1, 2, 3, 4};
    Object array[4]; // Object = void*，存储每个int的地址
    for (int i = 0; i < 4; i++) {
        array[i] = &data[i];
    }

    // 应用置换
    Object* result = cyclic->vtable->apply(cyclic, array, 4);

    if (result) {
        printf("原数组：");
        print_int_array(array, 4);
        printf("置换后：");
        print_int_array(result, 4);
        free(result);
    }
    cyclic->vtable->destroy(cyclic);
    printf("\n");
}

void test_composite_simplify() {
    printf("=== 测试组合置换simplify ===\n");
    // 创建两个轮换：M(1,2) 和 M(2,3)
    int cyclic1_pos[] = {1, 2};
    DisplaceExpression* cyclic1 = (DisplaceExpression*)CyclicDisplaceExpression_create(cyclic1_pos, 2);

    int cyclic2_pos[] = {2, 3};
    DisplaceExpression* cyclic2 = (DisplaceExpression*)CyclicDisplaceExpression_create(cyclic2_pos, 2);

    // 组合置换：cyclic1 → cyclic2
    DisplaceExpression* sub_exprs[] = {cyclic1, cyclic2};
    DisplaceExpression* composite = (DisplaceExpression*)CompositeDisplaceExpression_create(2, sub_exprs);

    // 化简
    DisplaceExpression* simplified = composite->vtable->simplify(composite);
    printf("组合置换化简后类型：");
    if (simplified->vtable == &s_cyclic_vtable) {
        printf("CyclicDisplaceExpression（最简轮换）\n");
    } else if (simplified->vtable == &s_composite_vtable) {
        printf("CompositeDisplaceExpression（多个轮换组合）\n");
    } else if (simplified->vtable == &s_empty_vtable) {
        printf("EmptyDisplaceExpression（恒等置换）\n");
    }

    // 释放资源（simplified是新实例，需释放；composite会释放子表达式）
    simplified->vtable->destroy(simplified);
    composite->vtable->destroy(composite);
    printf("\n");
}

int main() {
    test_cyclic_apply();
    test_composite_simplify();
    return 0;
}